/*
day179
2020.2.23
*/
#include<vector>
#include<iostream>
#include<set>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
		int sum=0;
		for(const int &i : nums){sum+=i;}
		if(sum%2 != 0) return false;
		int target=sum/2;
		
		set<int> set;
		set.insert(0);
		for(const int &i : nums)
		{
			vector<int> vec;
			for(const int &j : set)
			{
				int tem=j+i;
				if(tem==target) return true;
				if(tem<target && set.find(tem)==set.end())
				{
					vec.push_back(tem);
				}
			}
			set.insert(vec.begin(),vec.end());
		}
		return false;
    }
};

int main()
{
	vector<int> nums={1, 2, 3, 5};
	Solution s;
	cout<<s.canPartition(nums)<<endl;
	return 0;
}
